#ifndef _SPLAYTREE_H_
#define _SPLAYTREE_H_

#include <iostream>
#include <algorithm>
#include <vector>

/**
* @brief To complete the class of SplayTree and complete the function.
* 
*/
template <typename Comparable>
class SplayTree
{
    private:

        /**
        * @brief To construct the fundamantal structure of SplayNode
        * 
        */
        struct SplayNode
        {
            Comparable element;
            SplayNode *pre;
            SplayNode *left;
            SplayNode *right;

            SplayNode( const Comparable & theElement, SplayNode *pt, SplayNode *lt, SplayNode *rt )
                : element{ theElement }, pre{ pt }, left{ lt }, right{ rt } {}

            SplayNode( Comparable && theElement, SplayNode *pt, SplayNode *lt, SplayNode *rt)
                : element{ std::move( theElement ) }, pre{ pt }, left{ lt }, right{ rt } {}
        };

        SplayNode *root;

        /**
         * Internal method to insert into a subtree.
         * x is the item to insert.
         * t is the node that roots the subtree.
         * Set the new root of the subtree.
         */
        void insert( const Comparable & x, SplayNode * & t, SplayNode * & root )
        {
            if( t == nullptr )
                t = new SplayNode( x, nullptr, nullptr, nullptr );
            else if( x < t->element )
            {
                if( t->left != nullptr )
                    insert( x, t->left, root );
                else
                {
                    SplayNode * tx = new SplayNode( x, t, nullptr, nullptr );
                    t->left = tx;
                    Dosplay( tx, root );
                }
            }
            else if( t->element < x )
            {
                if( t->right != nullptr )
                    insert( x, t->right, root );
                else
                {
                    SplayNode * ty = new SplayNode( x, t, nullptr, nullptr );
                    t->right = ty;
                    Dosplay( ty, root );
                }
            }
            else
                ;  // Duplicate; do nothing
        }

        /**
         * Internal method to insert into a subtree.
         * x is the item to insert by moving.
         * t is the node that roots the subtree.
         * Set the new root of the subtree.
         */
        void insert( Comparable && x, SplayNode * & t, SplayNode * & root )
        {
            if( t == nullptr)
                t = new SplayNode{ std::move( x ), nullptr, nullptr, nullptr};
            else if( x < t->element )
            {
                if( t->left != nullptr )
                    insert( x, t->left, root );
                else
                {
                    SplayNode * tx = new SplayNode( std::move( x ), t, nullptr, nullptr );
                    t->left = tx;
                    Dosplay( tx, root );
                }
            }
            else if( t->element < x )
            {
                if( t->right != nullptr )
                    insert( x, t->right, root );
                else
                {
                    SplayNode * ty = new SplayNode( std::move( x ), t, nullptr, nullptr );
                    t->right = ty;
                    Dosplay( ty, root );
                }
            }
        }

        /**
         * Internal method to search the element x from t
         */
        SplayNode * contain( Comparable x, SplayNode * & t, SplayNode * & root )
        {
            if( t == nullptr )
                return nullptr;

            SplayNode * p = nullptr;
            if( x == t->element )
            {
                p = t;
                Dosplay( t, root );
            }
            else if( x > t->element )
                p = contain( x, t->right, root );
            else if( x < t->element)
                p = contain( x, t->left, root );
            else
                ;
            return p;
        }

        /**
         * Internal method to do splay operation on the tree
         */
        void Dosplay( SplayNode * & t, SplayNode * & root )
        {
            if( t == nullptr || t->pre == nullptr )
                return;
            
            while( t->pre != nullptr )
            {
                if( t->pre->pre == nullptr )
                {
                    if( t == t->pre->left )
                        SingleRightRotate( t, root );
                    else
                        SingleLeftRotate( t, root );
                }
                else
                {
                    SplayNode * father, * grandfather;
                    father = t->pre;
                    grandfather = father->pre;
                    if( father == grandfather->left)
                    {
                        if( t == father->left )
                            ZigZigDoubleLeft( t, root );
                        else ZigZagLeftRight( t, root );
                    }
                    else
                    {
                        if( t == father->left )
                            ZigZagRightLeft( t, root );
                        else ZigZigDoubleRight( t, root );
                    }
                }
            }
        }

        /**
         * Rotate binary tree node with right child.
         * For Splay trees, this is a single rotation for case 1.
         * Update heights, then set new root.
         */
        void SingleRightRotate( SplayNode * & t, SplayNode * & root )
        {
            SplayNode * tfa = t->pre;
            if( tfa == nullptr )
                return;
            bool judge = true;
            if( tfa == root )
                judge = false;
            
            if( t->right != nullptr )
                t->right->pre = tfa;
            tfa->left = t->right;
            t->right = tfa;
            t->pre = tfa->pre;
            tfa->pre = t;
            if( t->pre != nullptr )
                if( t->pre->element > t->element )
                    t->pre->left = t;
                else
                    t->pre->right = t;

            if( !judge ) root = t;
        }

        /**
         * Rotate binary tree node with left child.
         * For Splay trees, this is a single rotation for case 1.
         * Update heights, then set new root.
         */
        void SingleLeftRotate( SplayNode * & t, SplayNode * & root )
        {
            SplayNode * tfa = t->pre;
            if( tfa == nullptr )
                return;
            bool judge = true;
            if( tfa == root )
                judge = false;

            if( t->left != nullptr )
                t->left->pre = tfa;
            tfa->right = t->left;
            t->left = tfa;
            t->pre = tfa->pre;
            tfa->pre = t;
            if( t->pre != nullptr )
                if( t->pre->element > t->element )
                    t->pre->left = t;
                else
                    t->pre->right = t;

            if( !judge ) root = t;
        }

        /**
         * Rotate with the case of ZigZag on left->right
         */
        void ZigZagLeftRight( SplayNode * & t, SplayNode * & root )
        {
            SingleLeftRotate( t, root );
            SingleRightRotate( t, root );
        }

        /**
         * Rotate with the case of ZigZag on right->left
         */
        void ZigZagRightLeft( SplayNode * & t, SplayNode * & root )
        {
            SingleRightRotate( t, root );
            SingleLeftRotate( t, root );
        }

        /**
         * Rotate with the case of ZigZig on double left
         */
        void ZigZigDoubleLeft( SplayNode * & t, SplayNode * & root )
        {
            SingleRightRotate( t->pre, root );
            SingleRightRotate( t, root );
        }

        /**
         * Rotate with the case of ZigZig on double right
         */
        void ZigZigDoubleRight( SplayNode * & t, SplayNode * & root )
        {
            SingleLeftRotate( t->pre, root );
            SingleLeftRotate( t, root );
        }
    
        /**
         * Internal method to remove from a subtree.
         * x is the item to remove.
         * t is the node that roots the subtree.
         * Set the new root of the subtree.
         */
        void remove( const Comparable & x, SplayNode * & t )
        {
            if( t == nullptr )
                return;   // Item not found; do nothing
            if( x < t->element )
                remove( x, t->left );
            else if( t->element < x )
                remove( x, t->right );
            else if( t->left != nullptr && t->right != nullptr ) // Two children
            {
                t->element = findMin( t->right )->element;
                remove( t->element, t->right );
            }
            else
            {
                SplayNode *oldNode = t;
                t = ( t->left != nullptr ) ? t->left : t->right;
                delete oldNode;
            }
        }

        /**
         * Internal method to find the smallest item in a subtree t.
         * Return node containing the smallest item.
         */
        SplayNode * findMin( const SplayNode * & t ) const
        {
            if( t != nullptr )
                while( t->left != nullptr )
                    t = t->left;
            return t;
        }

        /**
         * Internal method to find the largest item in a subtree t.
         * Return node containing the largest item.
         */
        SplayNode * findMax( const SplayNode * & t ) const
        {
            if( t != nullptr )
                while( t->right != nullptr )
                    t = t->right;
            return t;
        }
        
        /**
        * Internal method to judge whether the tree is empty.
        * 
        */
        bool isEmpty( const SplayNode * & t )
        {
            if( t == nullptr)
                return true;
            else
                return false;
        }

        /**
         * Internal method to make subtree empty.
         */
        void makeEmpty( SplayNode * & t )
        {
            if( t != nullptr )
            {
                makeEmpty( t->left );
                makeEmpty( t->right );
                delete t;
            }
            t = nullptr;
        }

        /**
         * Internal method to print a subtree rooted at t in sorted order.
         */
        void printTree( const SplayNode * & t )
        {
            if( t != nullptr )
            {
                printTree( t->left );
                std::cout << t->element << " ";
                printTree( t->right );
            }
        }
        
        /**
         * Internal method to clone subtree.
         */
        SplayNode * clone( SplayNode * & t ) const
        {
            if( t == nullptr )
                return nullptr;
    
            SplayNode ret;
            ret = new SplayNode( t->element, nullptr, clone( t->left ), clone( t->right ) );
            ret.pre = t->pre;
            return ret;
        }

        /**
         * Internal method to recover the vector by the elements of SplaySearchTree in order.
         */
        void recover( std::vector<Comparable> &_obj, SplayNode * & t, int judge )
        {
            if( judge == 0)
                _obj.clear();
            if( t != nullptr)
            {
                recover( _obj, t->left, 1);
                _obj.push_back( t->element );
                recover( _obj, t->right, 1);
            }
        }

    public:
        /**
         * Construt and initialize a constructor
         */
        SplayTree( ) : root{ nullptr }
            {};

        /**
         * Copy constructor
         */
        SplayTree( const SplayTree & rhs ) : root{ nullptr }
        {
            root = clone( rhs.root );
        }

        /**
         * Copy constructor by moving
         */
        SplayTree( SplayTree && rhs )
        {
            root.element = rhs.root.element;
            root.pre = rhs.root.pre;
            root.left = rhs.root.left;
            root.right = rhs.root.right;
            delete rhs.root;
        }
        
        /**
         * Destructor for the tree
         */
        ~SplayTree( )
        {
            makeEmpty( );
        }
        
        /**
         * Find the smallest item in a subtree t.
         * 
         */
        const Comparable & finMin() const
        {
            return findMin( root )->element;
        }

        /**
         * Find the largest item in a subtree t.
         * 
         */
        const Comparable & finMax() const
        {
            return findMax( root )->element;
        }

        /**
        * Judge whether the tree is empty.
        * 
        */
        bool isEmpty() const
        {
            return isEmpty( root );
        }

        /**
         * Print the tree contents in sorted order.
         * 
         */
        void printTree()
        {
            if( isEmpty( ) )
                std::cout << "Empty tree" << std::endl;
            else
                printTree( root );
        }
        
        /**
         * Make subtree empty.
         */
        void makeEmpty()
        {
            makeEmpty( root );
        }

        /**
        * Insert x into the tree; duplicates are ignored.
        * Do splay on x to set it as root
        * 
        */
        void insert( const Comparable & x )
        {
            insert( x, root, root );
        }

        /**
        * Insert the type && x into the tree; duplicates are ignored.
        * Do splay on x to set it as root
        * 
        */
        void insert( Comparable && x )
        {
            insert( x, root, root );
        }

        /**
        * Remove x from the tree. Nothing is done if x is not found.
        * 
        */
        void remove( const Comparable & x )
        {
            remove( x, root );
        }

        /**
        * Check whether x is in the tree,
        * and do splay to set root as x if found
        * 
        */
        bool contain( Comparable x )
        {
            bool found = true;
            SplayNode * tree = contain( x, root, root );
            if( tree == nullptr )
                found = false;
            
            return found;
        }

        /**
         * Deep copy.
         */
        const SplayTree & operator=( const SplayTree & rhs )
        {
            if( this != &rhs )
            {
                makeEmpty( );
                root = clone( rhs.root );
            }
            return *this;
        }

        /**
         * Deep copy by swaping
         */
        SplayTree & operator=( SplayTree && rhs )
        {
            this.root.element = rhs.root.element;
            this.root.pre = rhs.root.pre;
            this.root.left = rhs.root.left;
            this.root.right = rhs.root.right;
            delete rhs.root;
            return *this;
        }

        /**
         * Insert the elements into the SplaySearchTree so that it is changed increasing.
         */
        void BST_sort( const std::vector<Comparable> &_obj )
        {
            if (root != nullptr)
                makeEmpty();
            int num = _obj.size();
            for (int i = 0; i < num; i++)
                insert( _obj[i], root, root );
        }

        /**
         * Recover the vector by the elements of SplaySearchTree in order.
         */
        void recover( std::vector<Comparable> &_obj)
        {
            recover( _obj, root, 0 );
        }
};

#else
// Do nothing.
#endif